class DoublyLinkedList<T> {

    private final Node header = new Node(null);

    void push(T data) {
        Node header = this.header;
        while(header.nextPointer != null) {
            header = header.nextPointer;
        }

        header.nextPointer = new Node(data);
    }

    T pop() {
        if (this.header.nextPointer == null)
            return null;

        Node header = this.header;
        Node before = this.header;
        while(header.nextPointer != null) {
            before = header;
            header = header.nextPointer;
        }

        before.nextPointer = null;
        return header.data;
    }

    T shift() {
        if (this.header.nextPointer == null)
            return null;

        Node shiftNode = this.header.nextPointer;
        this.header.nextPointer = shiftNode.nextPointer;
        return shiftNode.data;
    }

    void unshift(T data) {

        Node nextPointer = this.header.nextPointer;
        Node unShiftNode = new Node(data);
        unShiftNode.nextPointer = nextPointer;
        this.header.nextPointer = unShiftNode;
    }

    class Node {
        T data;
        Node nextPointer;

        Node(T data){
            this.data = data;
            this.nextPointer = null;
        }
    }
}